\documentclass[twocolumn]{svjour3}
\usepackage[utf8]{inputenc}

\usepackage{hyperref}
\usepackage{breakurl}
\usepackage{natbib}
\usepackage{subfigure}
\usepackage{mathtools}
\usepackage{amsfonts}
\let\vec\undefined
\usepackage{MnSymbol}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{nameref}

\hyphenation{STN-CONV}
\hyphenation{find-Near-est-Split-Ev-ent}
\hyphenation{get-Near-est-Merge-Ev-ent}
\hyphenation{get-Near-est-Split-Ev-ent}
\hyphenation{tem-po-ral-con-stra-int}
\hyphenation{ev-ent}

%\DeclareGraphicsExtensions{.eps}

\algnewcommand\algorithmicswitch{\textbf{switch}}
\algnewcommand\algorithmiccase{\textbf{case}}
% New "environments"
\algdef{SE}[SWITCH]{Switch}{EndSwitch}[1]{\algorithmicswitch\ #1}{\algorithmicend\ \algorithmicswitch}%
\algdef{SE}[CASE]{Case}{EndCase}[1]{\algorithmiccase\ #1}{\algorithmicend\ \algorithmiccase}%
\algtext*{EndSwitch}%
\algtext*{EndCase}%

\newcommand{\dist}[2]{d_{#1#2}}
\newcommand{\distij}{\dist{i}{j}}
\newcommand{\distji}{\dist{j}{i}}
\newcommand{\distik}{\dist{i}{k}}
\newcommand{\pij}{p_{ij}}
\newcommand{\eqg}{G_{\sigma}^{=}}
\newcommand{\aqg}{A_{\sigma}^{=}}
\newcommand{\eqtback}[1]{\overset{\twoheadleftarrow}{\rule{0pt}{1.2ex}\smash{\eqt}}(#1)}
\newcommand{\eqtforw}[1]{\overset{\twoheadrightarrow}{\rule{0pt}{1.2ex}\smash{\eqt}}(#1)}
\newcommand{\eqt}{\eqts{\sigma}}
\newcommand{\eqtw}{\widetilde{\eqtree}^{\sigma}}
\newcommand{\eqts}[1]{\eqtree^{#1}}
\newcommand{\eqtree}{\mathcal{T}}
\newcommand{\act}{\mathcal{O}}
\newcommand{\sg}{\widetilde{G}}
\newcommand{\sact}{\widetilde{\act}}
\newcommand{\sa}{\widetilde{A}}
\newcommand{\s}{\mathcal{S}^\sigma}
\newcommand{\f}{\mathcal{F}^\sigma}
%\newtheorem{theorem}{Theorem}
%\newtheorem{definition}{Definition}
%\newtheorem{lemma}{Lemma}
\newtheorem{notation}{Notation}
%\newproof{proof}{Proof}
\DeclareMathOperator*{\argmin}{arg\,min}

\algrenewcommand\algorithmicindent{5pt}

\tolerance=5000

\begin{document}
\title{Scheduling with Convex Cost Functions and Temporal Constraints}
%\subtitle{test}
\author{Vladimír Duša, Vladan Majerech}
\institute{Vladimír Duša \at Charles University, Faculty of Mathematics and Physics, Malostranské náměstí 25, Prague 1, 118~00, Czech Republic\\\email{dusa@ktiml.mff.cuni.cz}\and 
		   Vladan Majerech \\\email{maj@ktiml.mff.cuni.cz}
	}	
\keywords{scheduling \and simple temporal network \and termporal constraints \and convex cost functions}

\maketitle
	
\begin{abstract}
	This paper introduces scheduling of operations with convex cost functions and temporal constraints like "the activity can't start earlier than another activity is completed" or "the activity must not start later than some given time after completion of another activity", etc. The goal is to find the schedule with the cheapest total cost of all activities and satisfying all temporal constraints. The condition guaranteeing the optimality of the schedule is presented in the first part of the paper. After that, the polynomial algorithm which constructs the optimal schedule is demonstrated in a form of pseudocode. At the end the example of the algorithm functionality is presented.
\end{abstract}

\section{Introduction}
Nowadays optimal scheduling of resources is crucial in many areas of business. On-time completion of operations is a very common optimization criterion. Such criteria can be described by convex cost functions penalizing earlier and/or later completion of an operation. Precedence constraints which guarantee, that a certain operation cannot start before another operation has finished are necessary elements of real scheduling. An algorithm solving this problem was introduced in \citet{Chretienne:2003:PSC:642013.642023}. Contrary to \citet{Chretienne:2003:PSC:642013.642023}, the role of precedence constraints is extended in the following text: a certain operation cannot start before another operation has finished, but not later than the given time. Since a mistake was found in \citet{Chretienne:2003:PSC:642013.642023} (see \ref{sec:counterexample}), a new approach inspired by \citet{Chretienne:2003:PSC:642013.642023} is introduced in this work. Similar variants of this problem considering the earlines and tardines penaltis have been studied in \citet{Garey1988} and \citet{ROE:8227001}. Also variants discussing the time lags where an operation can't start earlier or later according to another operation have been introduced in \citet{Brucker199977} and \citet{so30629}.

First of all, the problem will be formally defined. Next, a special data structure will be designed and it will be proven that the existence of this structure guarantees the optimality of the schedule. An algorithm which construct an optimal schedule in polynomial time is presented in the second part of this work.

\section{Problem definition and condition of optimality}\label{sec:problemdefinition}
Let $\act=\{1,2,...n\}$ be a set of operations. For each $i\in\act$, $p_i$ denotes the processing time of operation $i$. A \emph{precedence graph}, that is, a directed acyclic graph $G=(\act, A)$, is also given. Let the variable $\distij \geq 0$ for each $(i,j)\in A$ denote the maximum possible distance between $end(i)$ and $start(j)$. If the maximum possible distance is not defined, we assume that $\distij=+\infty$. A \emph{schedule} is a function $\sigma: \mathcal{O}\rightarrow \mathbb{R}$. The value $\sigma(i)$ represents the start time of operation $i$. We say that schedule $\sigma$ is \emph{feasible} iff for all $(i,j)\in A$ it holds that $\sigma(j)\geq \sigma(i)+p_i$ and $\sigma(j) \leq \sigma(i) + p_i + \distij$. 
%Vladan navrhl aby cost funkce nebyly monotonní, abychom pak neměli v algoritmu problémy s úletem do nekonečna. Ale nám se o částech lineární funkce tvaru \__ nebo __/ budou v praxi hodit.
A convex function with finite minimum $c_i: \mathbb{R}\rightarrow\mathbb{R}$ associated with each operation $i\in\mathcal{O}$ will be called the \emph{cost function}. The value $c_i(t)$ is the cost of operation $i$ if it starts at time $t$. The cost of a schedule $\sigma$ is then defined as follows:
$$c(\sigma) = \sum_{i\in \act}{c_i(\sigma(i)})$$

The goal is to find a feasible schedule $\sigma$ with lowest $\sum_{i\in \mathcal{O}}c(\sigma(i))$.

\subsection{Problem transformation into STN}\label{sec:problemtransformation}
The problem would be simpler, if it included no maximum possible distance $\distij$. Such a formulation can be achieved by adding a new special edge $(j,i)$ for each $(i,j)$ with $d_{ij}<+\infty$ into graph $G$. 

Let us define this idea formally: We introduce a new variable $\pij$ for each edge $(i,j)\in A$ and we set $p_{ij} := p_i$. The variable $p_{ij}$ represents the minimum possible distance between $start(i)$ and $start(j)$ (the length of an operation is now represented by evaluation of an edge). For each edge with $\distij<\infty$ a new edge $(j,i)$ is added into graph $G$ and $p_{ji}=-p_i-\distij$ is set (see figure \ref{fig:problemtransformation}). As a consequence of this transformation we have to redefine the temporal constraints: We now have $\sigma(j) \geq \sigma(i) + p_{ij}$ for each $(i,j)\in A$.

\begin{figure}
	\caption{Problem transformation}\label{fig:problemtransformation}
	\centering
\includegraphics[scale=0.8]{Fig1}
\end{figure}

This new definition of the problem is equivalent with the former one, because $\forall (i,j)\in A$ is $\sigma(j) \geq \sigma(i) + \pij = \sigma(i) + p_i$ and $\forall (i,j)\in A : d_{ij}<\infty$ is a new edge $(j,i)$, for which $\sigma(i) \geq \sigma(j) + p_{ji} = \sigma(j) - p_i - \distij \Rightarrow \sigma(j)\leq \sigma(i)+p_i+\distij$. Graph $G$ now represents a simple temporal network. Using the $\alpha$, $\beta$, $\gamma$ notation of \citet{Brucker19993}, the problem may be denoted by $P\infty | \mathit{temp}, f_j \mathit{ convex} | \sum f_j$.

Terms $p_i$ and $\distij$ are no longer necessary and will not be used in the following text.

The tuple $(G,p,c)$ will be called an instance of STNCONV.

The problem definition contains activity $0$ preceding all activities in $\mathcal{O}$ and having $\sigma(0)=0$ in the original article \citet{Chretienne:2003:PSC:642013.642023}. It guarantees $\sigma(i)\geq 0$ for each $i\in \mathcal{O}$. This behaviour can be simulated in STNCONV by creating an activity with a cost function with a very cheap minimum in $\sigma(0)$.

\subsection{Schedule optimality condition}
A sufficient condition guaranteeing the optimality of a schedule $\sigma$ will be shown in this section. First of all, some general definitions will be introduced. A structure called an \emph{active equality tree} will then be defined, and it will be proven that a better schedule cannot be obtained by tearing this tree into more pieces (i.e. shifting some operations to the left and/or some operations to the right). Finally, we will show that whenever we are able to cover all operations by on-time disjoint active equality trees, we have an optimal schedule.

\subsubsection*{Graph theory review}
Let us first recall some common terms from graph theory.

\begin{definition}
	Let $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ be graphs. Then $G=G_1 \cup G_2$ defined as $G=(V_1 \cup V_2, E_1 \cup E_2)$ is called a \textbf{graph union}.
\end{definition}

\begin{definition}
	Let $G=(V, E)$ be a graph and let $\widetilde{V}\subseteq V$, then we say that graph $G(\widetilde{V})=(\widetilde{V}, (\widetilde{V} \times \widetilde{V}) \cap E)$ is a \textbf{subgraph} of G \textbf{induced} on $\widetilde{V}$.
\end{definition}

\begin{definition}
	Let $G=(V, E)$ be a graph, and let $\widetilde{G}=(\widetilde{V}, \widetilde{E})$ be a subgraph of $G$. \textbf{Graph subtraction} will be defined as $G-\widetilde{G}=G(V-\widetilde{V})$.
\end{definition}

\begin{definition}
	We say that graphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ are \textbf{disjoint graphs} if $V_1\cap V_2=\emptyset$.
\end{definition}

\subsubsection{General properties of a subgraph of $G$}
In this section we will introduce some properties of a subset of operations in a schedule (i.e. a subgraph of $G$). Let us consider whether a better schedule could be obtained by shifting some operations to the right or to the left. First of all, we will define what we mean by "shift some operations". In order to simplify notation in the following text, we will work not with a set of activities but with whole subgraphs $\sg=(\sact,\sa)\subseteq G$, even though $\sa$ is of no importance in the following definitions. Its importance will become evident in section \ref{sec:equalitygraphsandtrees}.

\begin{definition}
	Let $(G,p,c)$ be an instance of the problem STNCONV and let $\sigma$ be a schedule and let $\sg=(\sact,\sa)$ be a subgraph of $G$. Schedule $\sigma'$ is called a \textbf{shift of $\sg$} if $\exists t \in\mathbb{R}$ such that $\sigma'(i)=\sigma(i)+t$ $\forall i\in \sact$ and $\sigma'(i)=\sigma(i)$ $\forall i\notin \sact$. We talk about a \textbf{forward shift} of $\widetilde{G}$ if $t>0$ and a \textbf{backward shift} for $t<0$.
\end{definition}

\begin{definition}\label{def:sigma_cost}
	Let $(G,p,c)$ be an instance of the problem STNCONV and $\sigma$ be a schedule. Let $\sg=(\sact, \sa)$ be a subgraph of $G$. Then the \textbf{start time} $\sigma(\sg)$ of graph $\sg$ is defined as $\min_{i\in \sact} \sigma(i)$. The \textbf{shift cost function} $sc_{\sg}(t)$ of graph $\sg$ is $sc_{\sg}(t) = \sum_{i\in \sact}c_i (t + \sigma(i))$. 
\end{definition}

Since $c_i$ are convex in definition \ref{def:sigma_cost}, the shift cost function $sc_{\sg}(t)$ of each $\sg$ is also convex. In order to analyse the position of $\sg$ in time, we will introduce the following terms.

\begin{definition}\label{def:late_early_etc}
	Let $(G,p,c)$ be an instance of the problem STNCONV and let $\sigma$ be a schedule. Let $\sg=(\sact, \sa)$ be a subgraph of $G$. We say, that $\sg$ is \textbf{early} iff $\forall t\leq 0$ it holds that $sc_{\sg}(t) \geq sc_{\sg}(0)$. We say, that $\sg$ is \textbf{late} iff $\forall t\geq 0$ it holds that $sc_{\sg}(t) \geq sc_{\sg}(0)$. $\sg$ that is not late (resp. early) is \textbf{strictly early} (resp. \textbf{strictly late}). $\sg$, that is early and late at the same time is called \textbf{on-time}.
\end{definition}

In other words $\sg$ is
\begin{itemize}
\item \emph{early} if the schedule will not get better by shifting $\sg$ backwards (see lemma \ref{lemma:AETShift})
\item \emph{strictly early} if the schedule will get better by shifting $\sg$ forwards (see lemma \ref{lemma:lateshift})
\item \emph{on-time} if the schedule will not get better by shifting $\sg$ either backwards or forwards.
\item analogically for \emph{late} and \emph{strictly late} 
\end{itemize}

Let us describe the above-introduced notes formally:

\begin{lemma}\label{lemma:AETShift}
	Let $\sigma$ be a schedule of instance $(G,p,c)$ of a STNCONV problem and let $\widetilde{G}$ be an early (resp. late) subgraph of $G$ in $\sigma$. Let $\sigma'$ be a schedule where $\widetilde{G}$ is shifted backwards (resp. forwards). Then it holds that $c(\sigma)\leq c(\sigma')$.
\end{lemma}
\begin{proof}
	Since $\widetilde{G}$ is early in $\sigma$, then $\forall t\leq 0$ it holds that $sc_{\widetilde{G}}(t)\geq sc_{\widetilde{G}}(0)$.
	 Let $t \leq 0$, then $c(\sigma) = sc_{\widetilde{G}}(0) + sc_{G-\widetilde{G}}(0) \leq  sc_{\widetilde{G}}(t) + sc_{G-\widetilde{G}}(0) =c(\sigma')$. The case for late $\widetilde{G}$ can be proven analogically.
\end{proof}

\begin{lemma}\label{lemma:lateshift}
	Let $\sigma$ be a schedule of instance $(G,p,c)$ STNCONV and let $\widetilde{G}$ be a strictly early (resp. strictly late) subgraph of $G$ in $\sigma$. Then there exists schedule\footnote{schedule $\sigma'$ do not need to be feasible.} $\sigma'$, where $\widetilde{G}$ is shifted forwards (resp. backwards) and it holds that $c(\sigma')<c(\sigma)$.
\end{lemma}
\begin{proof}
From definition \ref{def:late_early_etc} it follows that a graph is strictly early when it is not late. Thus there exists such $t>0$ for which $sc_{\widetilde{G}}(t) < sc_{\widetilde{G}}(0)$, then $c(\sigma') = sc_{\widetilde{G}}(t) + sc_{G-\widetilde{G}}(0) < sc_{\widetilde{G}}(0) + sc_{G-\widetilde{G}}(0) =c(\sigma)$. The case for strictly late $\widetilde{G}$ can be proven analogically.
\end{proof}
	
We will show in lemma \ref{lemma:earlygraphs} (resp. lemma \ref{lemma:strictlyearlygraphs}) that a union of disjoint early (resp. strictly early) graphs is also an early (resp. strictly early) graph (of course the statement holds for late graphs). These two statements will be crucial in the subsequent proof of the schedule optimality condition afterwards.

\begin{lemma}\label{lemma:earlygraphs}
		Let $\sigma$ be a schedule of instance $(G,p,c)$ STNCONV and let $G_1$ and $G_2$ be early (resp. late) disjoint subgraphs of $G$, then graph $\widetilde{G}=G_1 \cup G_2$ is also early (resp. late).
\end{lemma}
\begin{proof}
	Since $G_1$ and $G_2$ are early, then according to definition \ref{def:late_early_etc}:\\
	$\forall t\leq 0$ it holds that $sc_{G_1}(t) \geq c_{G_1}(0)$\\
	$\forall t\leq 0$ it holds that $sc_{G_2}(t) \geq c_{G_2}(0)$\\
It easily follows, that $\forall t\leq 0$ it holds that $sc_{\widetilde{G}}(t) = sc_{G_1}(t) + sc_{G_2}(t) \geq sc_{G_1}(0) + sc_{G_2}(0) = sc_{\widetilde{G}}(0)$.

The case for late graphs can be proven analogically.

\end{proof}

\begin{lemma}\label{lemma:strictlyearlygraphs}
		Let $\sigma$ be a schedule of instance $(G,p,c)$ STNCONV and let $G_1$ and $G_2$ be strictly early (resp. strictly late) disjoint subgraphs of $G$, then graph $\widetilde{G}=G_1 \cup G_2$ is also strictly early (resp. strictly late).
\end{lemma}
\begin{proof}
	 Definition \ref{def:late_early_etc} posts that a graph is strictly early when it is not late. Thus:\\
	$\exists t_{G_1} > 0$ such that $c_{G_1}(t_{G_1}) < c_{G_1}(0)$\\
	$\exists t_{G_2} > 0$ such that $c_{G_2}(t_{G_2}) < c_{G_2}(0)$\\
Since $sc_{\widetilde{G}}$ is convex, then if there exists $t>0$ for which $sc_{\widetilde{G}}(t) < sc_{\widetilde{G}}(0)$, then $\forall u\in (0,t]$ it holds that $sc_{G}(u)\leq sc_{G}(0)$.	Thus we choose $t=\min\{t_{G_1}, t_{G_2}\}$. Now $sc_{\widetilde{G}}(t) = sc_{G_1}(t) + sc_{G_2}(t) < sc_{G_1}(0) + sc_{G_2}(0) = sc_{\widetilde{G}}(0)$.
	The case for strictly late graphs can be proven analogically.
\end{proof}

\subsubsection{The equality graph and equality trees}\label{sec:equalitygraphsandtrees}
Henceforth also temporal constraints will also be taken into account. Subgraphs having a certain structure according to schedule $\sigma$  will be introduced in this section. These subgraphs, called active equality trees, will help us to prove the optimality of schedule $\sigma$.

\begin{definition} %Equality graph
	Let $(G,p,c)$ be an instance of the problem STNCONV and let $\sigma$ be a schedule. The \textbf{equality graph} of $\sigma$, denoted $\eqg$, is the graph $(\act, \aqg)$ where $\aqg=\{(i,j)\in A | \sigma(j)-\sigma(i)=\pij\}$.
\end{definition}

In other words, if all temporal constraints between operations not `touching` each other (or if they are not `stretched` to the maximum, in the case of $p_{ij}<0$) in schedule $\sigma$ are removed from the graph $G$, then we get an equality graph.

\begin{definition} %Spanning equality tree
	Let $(G,p,c)$ be an instance of the problem STNCONV and let $\sigma$ be a schedule. Let $\eqt$ be a subgraph of $\eqg$. If $\eqt$ is a tree\footnote{We now ignore the orientation of edges and consider them as if they all were undirected.}, then we call $\eqt$ an \textbf{equality tree}.
\end{definition}

\begin{notation}
Since $\eqt$ is a tree, it will be split into two components after removing an arbitrary edge $(i,j)\in A_{\eqt}$. Let us denote these two components $\eqtback{(i,j)}$ and $\eqtforw{(i,j)}$, where $\eqtback{(i,j)}$ contains operation $i$ and $\eqtforw{(i,j)}$ contains operation $j$.
\end{notation}

\begin{definition}
  Let $\eqt=(\act_{\eqt},A_{\eqt})$ be an equality tree. Any edge $(i,j)\in A_{\eqt}$, for which either	$\eqtback{(i,j)}$ is strictly early and $\eqtforw{(i,j)}$ is late or, $\eqtback{(i,j)}$ is early and $\eqtforw{(i,j)}$ is strictly late or, $\eqtback{(i,j)}$ is strictly early and $\eqtforw{(i,j)}$ is strictly late is called an \textbf{active edge}.
\end{definition}

In other words, an edge $(i,j)$ is active if there is a real `press` (or `pull` in the case of $\pij<0$) between trees $\eqtback{(i,j)}$ and $\eqtforw{(i,j)}$ connected by this edge\footnote{The main difference from the definition of an active edge in article \citet{Chretienne:2003:PSC:642013.642023} is, that the edge is not active, if $\eqtback{(i,j)}$ and $\eqtforw{(i,j)}$ are both on-time. For more information see \ref{sec:counterexample}.}.

\begin{definition}
	We say that an equality tree $\eqt=(\act_{\eqt},A_{\eqt})$ is an \textbf{active equality tree} if all edges in $A_\eqt$ are active.
\end{definition}

An active equality tree is a structure where each edge is either "under pressure" or is "resisting tearing". We will show in the following text that it is not worth tearing any active equality tree into more pieces in order to get a better schedule.

\subsubsection{Schedule optimality condition}
Let us consider an arbitrary active equality tree $\eqt$, which is on-time. There is a question whether schedule  $\sigma$ can be improved by shifting (some) operations from $\eqt$. We could shift the whole $\eqt$, but it has been shown in lemma \ref{lemma:AETShift} that shifting of an on-time subgraph does not improve the schedule. We will show in lemma \ref{lemma:roztrzeni} that tearing $\eqt$ into more pieces and shifting them separately also does not improve schedule $\sigma$.

Before we proceed to the final lemma \ref{lemma:roztrzeni}, we will prove the following statement, which will help us to prove the lemma.

\begin{lemma}\label{lemma:EarlySubtree}
	Let $\eqt=(\act_{\eqt},A_{\eqt})$ be an active equality tree. Let $P\subseteq A_{\eqt}$ such that $\forall (i,j)\in P$ $\forall(\tilde{i}, \tilde{j})\in P: ((i,j) \neq (\tilde{i},\tilde{j}))$, $\eqtforw{(i,j)}$ and $\eqtforw{(\tilde{i},\tilde{j})}$ are disjoint (see figure \ref{fig:earlysubtree}). Let $T=\bigcup_{(i,j)\in P}\eqtforw{(i,j)}$, then $\eqt - T$ is early. 
	
	Analogically let $P\subseteq A_{\eqt}$ such that $\forall (i,j)\in P$ $\forall(\tilde{i}, \tilde{j})\in P: ((i,j) \neq (\tilde{i},\tilde{j}))$, $\eqtback{(i,j)}$ and $\eqtback{(\tilde{i},\tilde{j})}$ are disjoint. Let $T=\bigcup_{(i,j)\in P}\eqtback{(i,j)}$, then $\eqt - T$ is late.
	
\end{lemma}
\begin{figure}
\caption{Active equality tree from lemma \ref{lemma:EarlySubtree}}\label{fig:earlysubtree}
\centering 
\includegraphics[scale=0.45]{Fig2}
\end{figure}
\begin{proof}
Our goal is to show that $\eqt-T$ is early. We will prove the lemma by contradiction: we will assume the opposite and then show that $\eqt$ could not be an active equality tree:

Let $\eqt-T$ be strictly late. Since $\eqt$ is an active equality tree, all edges in $P$ are active. It follows that all $\eqtree \in T$ are late or strictly late. We will now discuss both cases:
\begin{itemize}
\item Let us assume that there exists a tree $\eqtree$ in $T$ that is not strictly late, but just late. Without a loss of generality we choose $\eqtree$ as $\eqtforw{(i_1,j_1)}$ (see figure \ref{fig:earlysubtreeproof}).
\begin{figure}
	\caption{Proof of lemma \ref{lemma:EarlySubtree}}\label{fig:earlysubtreeproof}
	\centering
	\includegraphics[scale=0.45]{Fig3}
\end{figure}
In this case the edge marked by a star cannot be active, because it connects a graph that is not strictly early with a graph that is not strictly late.
\item If all $\eqtree \in T$ were strictly late, then according to lemma \ref{lemma:strictlyearlygraphs} no edge in $P$ could be active.
\end{itemize}
It follows that if $\eqt - T$ is strictly late, then $\eqt$ could not be an active equality tree, which is in contradiction with the assumption of the lemma. Thus $\eqt-T$ must be early.

The other case, where $\eqt - T$ is late, follows from symmetry.
\end{proof}

We need to define the terms \emph{path} in a directed graph, \emph{set of predecessors} and \emph{successors} of an operation, and \emph{forward} and \emph{backward closure} of a set of operations before posting the last lemma.

\begin{definition}
	Let $G=(V, E)$ be a directed graph. The sequence of nodes $p_G=\langle v_1, \ldots,v_n \rangle$ in $G$, such that $\forall i\in \{1,\ldots,n-1\}$, $(v_i, v_{i+1})\in E$ is called a \textbf{path in graph $G$}. The path $p_G=\langle v_1, \ldots, v_n \rangle$ from node $v_1$ to node $v_n$ is denoted as $v_1 \overset{p_G}{\leadsto} v_n$.
\end{definition}

\begin{definition}\label{def:predecessorssuccessors}
	Let $G=(V,E)$ be a directed graph. We denote a \textbf{set of all successors} (resp. \textbf{set of all predecessors}) \textbf{of an operation $i\in V$ in graph $G$} as
$$\overrightarrow{V_G}(i)=\{j\in V | \exists p_G : i \overset{p_G}{\leadsto} j \}$$
$$\overleftarrow{V_G}(i)=\{j\in V | \exists p_G : j \overset{p_G}{\leadsto} i \} $$ 
\end{definition}

Since $\langle i \rangle$ is also a path (of zero length), the set of all successors $\overrightarrow{V_G}(i)$ (resp. predecessors $\overleftarrow{V_G}(i)$) also contains operation $i$.

In order to keep the schedule feasible, whenever an operation $i$ from some $\eqt$ is shifted forwards by some $\delta$, all operations in $\overrightarrow{\act_\eqt}(i)$ must also be shifted forwards by at least $\delta$ (analogically for $\overleftarrow{\act_\eqt}(i)$ during backward shift). Let us also note, that a successor of an operation $i$ can be an operation $j$, for which $\sigma(j)<\sigma(i)$. This happens whenever $\pij<0$.

We will now define a graph induced on a set of vertices and all theirs direct and indirect predecessors (resp. successors), and we will call it \emph{forward closure} (resp \emph{backward closure}).

\begin{definition}
	Let G=(V,E) be a directed graph and let $\widetilde{V}\subseteq V$. We say that the graph $\overleftarrow{G}(\widetilde{V}) = G(\bigcup_{i\in\widetilde{V}} \overleftarrow{V_G}(i))$ is a \textbf{backward closure} of graph $G$ relative to $\widetilde{V}$. A \textbf{forward closure} of graph $G$ relative to $\widetilde{V}$ is defined as $\overrightarrow{G}(\widetilde{V}) = G(\bigcup_{i\in\widetilde{V}} \overrightarrow{V_G}(i))$.
\end{definition}

Let us note that a closure of graph $G$ relative to $\widetilde{V}$ always contains $\widetilde{V}$ as well.

We will now show, that a schedule cannot be improved by choosing a proper set of operations from an active equality tree (that do not necessarily need to be on-time) and shifting them forwards or backwards. 
\begin{figure}
	\caption{Splitting of an active equality tree}\label{fig:roztrzeni}
	\centering
	\includegraphics[scale=0.7]{Fig4}
\end{figure}


\begin{lemma}\label{lemma:roztrzeni}
Let $\eqt=(\act_{\eqt},A_{\eqt})$ be an active equality tree for which $A_{\eqt}\neq\emptyset$. Let $B\subseteq \act_{\eqt}$ (resp. $F\subseteq \act_{\eqt}$) such that $\overleftarrow{\eqt}(B)\neq\eqt$ (resp. $\overrightarrow{\eqt}(F)\neq\eqt$). Then $\overleftarrow{\eqt}(B)$ is early (resp. $\overrightarrow{\eqt}(F)$ is late).
\end{lemma}
\begin{proof}
	Let us consider an arbitrary component $C=(\act_C,A_C)$ of $\overleftarrow{\eqt}(B)$ separately (see figure \ref{fig:roztrzeni}).
	
	 Let $T=(\act_T,A_T)=\eqt-C$. Since each predecessor of each operation in $C$ is also in $C$, there is no "incoming" temporal constraint from $T$ to $C$: Formally, there is no $(i,j)\in A_{\eqt}$ such that $i\in \act_T$ and $j\in \act_C$. 

	 Let us consider all "outgoing" temporal constraints from $C$ to $T$: Formally, let $P=\{(i,j)\in A_{\eqt} |  i\in\act_C$ and $j\in \act_T\}$. Let us consider two temporal constraints $(i,j), (\widetilde{i},\widetilde{j})\in P: j \neq \widetilde{j}$. Since $C$ is a component\footnote{Directions are now being ignored.}, $i$ and $\widetilde{i}$ are connected in $C$. As $\eqt$ is a tree, the connecting path is unique. Therefore $\eqtforw{(i,j)}$ and $\eqtforw{(\widetilde{i},\widetilde{j})}$ are disjoint. As $C=\eqt - T$, from lemma \ref{lemma:EarlySubtree} follows that $C$ is early.
	Since all components of $\overleftarrow{\eqt}(B)$ are disjoint, according to lemma \ref{lemma:earlygraphs}, $\overleftarrow{\eqt}(B)$ is early. 
	
	The case for $\overrightarrow{\eqt}(F)$ can be proven analogically.
\end{proof}

Lemma \ref{lemma:roztrzeni} has shown that an arbitrary tearing of an active equality tree $\eqt$ preserving feasibility does not improve schedule $\sigma$. This leads us to the idea of covering the whole schedule with active equality trees. This idea will be stated in the following paragraph.

\begin{definition}
	Let $(G,p,c)$ be an instance of the problem STNCONV, let $\sigma$ be a schedule and $G=(\act, A)$. Let $\f=(\act_{\f}, A_{\f})=\bigcup_{l=1}^{k} \eqt_l$ be the union of $k$ disjoint active equality trees such that $\act_{\f}=\act$. We then call $\f$ an \textbf{active equality forest for $\sigma$}.
\end{definition}

\begin{definition}
	Let $\f$ be an active equality forest for $\sigma$, where each $\eqt\in \f$ is on-time, we we call $\f$ an \textbf{on-time active equality forest for $\sigma$}.
\end{definition}

In other words, an on-time active equality forest is a covering of the whole graph $G$ by disjoint active equality trees that are on-time.

\begin{theorem}\label{theorem:optimal}
	Let us consider any feasible schedule $\sigma$ of the instance $(G,p,c)$. Whenever there exists an on-time active equality forest $\f$, then $\sigma$ is optimal.
\end{theorem}
\begin{proof}
Let us choose the set $B\subseteq\act$ (resp. $F\subseteq\act$). Let us consider an arbitrary component $C$ of $\overleftarrow{\f}(B)$. Since $\f$ is the union of disjoint active equality trees, all of $C$ is a subgraph of some active equality tree $\eqt$. Now either $C=\eqt$, then $C$ is early, because $\eqt$ is on-time\footnote{Let us recall that "on-time" means early and late at the same time (see definition \ref{def:late_early_etc})}. Or $C\neq\eqt$, then $C$ is early by lemma \ref{lemma:roztrzeni}. So $\overleftarrow{\f}(B)$ is early (resp. $\overrightarrow{\f}(F)$ is late) by lemma \ref{lemma:earlygraphs}. Thus no shifting of an arbitrary set of operations will improve schedule $\sigma$.
\end{proof}

\section{Algorithm}
The condition shown in the previous text guarantees the optimality of an existing schedule. How to get such a feasible schedule for the graph $(\act, A)$ given in section \ref{sec:problemdefinition} will be the subject of the following text.

\subsection{Introduction}
Before beginning with a detailed description of the algorithm, we will briefly describe its main principles.

The data structure $\s=(\act_{\s}, A_{\s}, \f_{\s})$ maintaining an optimal feasible schedule will be used. This data structure implements methods for the insertion of operations and temporal constraints. $\act_{\s}$ contains the set of all activities inserted into $\s$, $A_{\s}$ contains the set of all temporal constraints inserted into $\s$. $\f_{\s}$ maintains the set of equality trees that will satisfy the definition of an active equality forest for $\sigma$ on $(\act_{\s}, A_{\s})$ after the insertion of each operation and temporal constraint.

At the beginning $\act_{\s}$, $A_{\s}$ and $\f_{\s}$ are empty sets. When an activity is inserted into $\act_{\s}$, a new active equality tree containing just the activity is created in $\f_{\s}$ and is placed in its optimum. So $\f_{\s}$ remains an on-time active equality forest for $\sigma$ on $(\act_{\s}, A_{\s})$ after the insertion of an activity.

Temporal constraints are inserted to $\f_{\s}$ as follows: if the temporal constraint $(i,j)$ currently being inserted into $A_{\s}$ is not violated, then it is not necessary to do anything - $\f_{\s}$ remains an on-time active equality forest. If $(i,j)$ is violated, then the tree from $\f_{\s}$ containing operation $j$ is shifted forward till $\sigma(j)=\sigma(i)+p_{ij}$. At this moment, $(i,j)$ is inserted into $A_{\s}$. The tree containing operation $j$ need not be on-time now. In this case it is shifted backwards. The shift of an equality tree is made in such a way that no temporal constraint becomes violated, and all equality trees $\f_{\s}$ are on-time equality trees except for the tree being shifted. This shift procedure creates the core of the algorithm and will be precisely described later. The temporal constraint $(i,j)$ cannot be inserted into $\s$ earlier than operations $i$ and $j$. Except for this limitation, operations and temporal constraints can be inserted into the schedule in an arbitrary order. The schedule for a given graph $(\act, A)$ can be obtained by inserting all operations and then all temporal constraints into $\s$.


Since the term "tree containing activity $i$" is often used in describing the algorithm, we will introduce the following notation:
\begin{notation}
	Let $\f_{\s}$ be an equality forest for $\sigma$. Since equality trees in $\f_{\s}$ are disjoint, the tree from $\f_{\s}$ containing operation $i$ will be denoted $\eqt_{i}$.
\end{notation}

\subsection{Algorithm}
Since the algorithm is presented in pseudocode, some implementation details are ignored. We will use the terminology from section \ref{sec:problemtransformation}, and thus the temporal constraints, are considered in the sense of STN. All procedures presented in this section are assumed to be implemented over structure $\s$. Thus we will write, for example, just $\textsc{insertOperation}(i)$ instead of $\textsc{insertOperation}(i,\s)$.

Let us now describe the algorithm in detail. Procedure \textsc{insertOperation}() (see algorithm \ref{alg:insertoperation}) creates a new equality tree containing just one operation (line \ref{alg:insertoperation:newopstart}-\ref{alg:insertoperation:newopend}). The tree is then shifted to its optimum (line \ref{alg:insertoperation:maketreeontime}).

\begin{algorithm}
\caption{Inserting a new operation into $\s$}\label{alg:insertoperation}
\begin{algorithmic}[1]
\Procedure{insertOperation}{$i$}
	\State $\sigma(i)=0$
	\State $\act_{\s}=\act_{\s}\cup \{i\}$\label{alg:insertoperation:newopstart}
	\State create new $\eqt \gets (\{i\}, \emptyset)$
	\State $\f_{\s} = \f_{\s} \cup \{\eqt\}$\label{alg:insertoperation:newopend}
	\State \textsc{makeTreeOnTime}($\eqt$)\label{alg:insertoperation:maketreeontime}
\EndProcedure
\end{algorithmic}
\end{algorithm}

The insertion of a temporal constraint $(i,j)$ is performed by procedure \textsc{insertTemporalConstraint}() (see algorithm \ref{alg:insertTemporalConstraint}). If the temporal constraint is not violated, it is merely inserted to the set of temporal constraints (line \ref{alg:insertTemporalConstraint:justadd}). Otherwise, operation $j$ must be shifted forward enough such that the temporal constraint can be inserted into the schedule (line \ref{alg:insertTemporalConstraint:shift} and \ref{alg:insertTemporalConstraint:add}), then tree $\eqt_j$ is shifted to its optimum (line \ref{alg:insertTemporalConstraint:makeontime}). As a last step, procedure \textsc{activate}() is called on line \ref{alg:insertTemporalConstraint:activate}. This procedure is not important at the moment and will be explained later. An example presenting \textsc{insertTemporalConstraint}() can be found on page \pageref{sec:example}.

\begin{algorithm}
\caption{Insertion of a temporal constraint into $\s$}\label{alg:insertTemporalConstraint}
\begin{algorithmic}[1]
\Procedure{insertTemporalConstraint}{$(i,j)$}
	\If{$i\notin A_{\s}$ \textbf{or} $j\notin A_{\s}$}
		\State throw exception 'Predecessor or successor is missing in $\act_{\s}$'
	\EndIf
	\If{$(i,j)$ is violated}
		\State \textsc{shift}($j$, '$\sigma(j)=\sigma(i)+p_{ij}$', $(i,j)$) \label{alg:insertTemporalConstraint:shift}
		\State $A_{\s}=A_{\s}\cup\{(i,j)\}$ \label{alg:insertTemporalConstraint:add}
		\State \textsc{makeTreeOnTime}($\eqt_j$)\label{alg:insertTemporalConstraint:makeontime}
		\State \textsc{activate}($\eqt_j$)\label{alg:insertTemporalConstraint:activate}			
	\Else
		\State $A_{\s}=A_{\s}\cup\{(i,j)\}$ \label{alg:insertTemporalConstraint:justadd}
	\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

The procedure \textsc{makeTreeOnTime}() (see algorithm \ref{alg:maketreeontime}) is used in previous procedures. The purpose of this procedure is to shift the tree containing the given operation into its optimum.

\begin{algorithm}
\caption{Shifting of a tree to its optimum}\label{alg:maketreeontime}
\begin{algorithmic}[1]
\Procedure{makeTreeOnTime}{$i$}
	\State \textsc{shift}($i$, '$\eqt_i$ is on-time', nothing);
\EndProcedure
\end{algorithmic}
\end{algorithm}

Let us introduce the definition of active edge used in \citet{Chretienne:2003:PSC:642013.642023}, before we describe procedure \textsc{shift}(). Since the term "active edge" has already been used in our article, we will call it \emph{weakly active edge} here:

\begin{definition}
  Let $\eqt=(\act_{\eqt},A_{\eqt})$ be an equality tree. Any edge $(i,j)\in A_{\eqt}$, for which $\eqtback{(i,j)}$ is early and $\eqtforw{(i,j)}$ is late is called a \textbf{weakly active edge}.
\end{definition}

\begin{definition}
	We say that equality tree $\eqt=(\act_{\eqt},A_{\eqt})$ is a \textbf{weakly active equality tree} if all edges in $A_{\eqt}$ are weakly active.
\end{definition}

\begin{definition}
	Let $\eqt=(\act_{\eqt},$ $A_{\eqt})$ be a weakly active equality tree and let $\widetilde{A}_{\eqtw}=\{(i,j)\in A_{\eqt} : \text{is active in }\eqt\}$. If each component of graph $\eqtw=(\act_{\eqt},\widetilde{A}_{\eqtw}$) is an active equality tree, then we will call $\eqt$ a \textbf{semi-active equality tree}.
\end{definition}

\begin{definition}
	Let $\eqt=(\act_{\eqt},A_{\eqt})$ be a semi-active equality tree. Let each component of graph $\eqtw$ from previous definition is on-time. Then we say that $\eqt$ is \textbf{c-on-time semi-active equality tree}.
\end{definition}

It is obvious that the schedule of a graph covered by an c-on-time semi-active equality tree is optimal. On the other hand, covering by an on-time weakly active equality tree or on-time semi-active equality tree doesn't ensure optimality (see \ref{sec:counterexample} for more information).

The core of the algorithm is comprised of procedure \textsc{shift}() (see algorithm \ref{alg:shift}). This ensures that the given operation $i$ is shifted in a such way, that the given criteria is satisfied, and the set of active equality trees $\f_{\s}$ still covers all operations by on-time active equality trees except for the tree $\eqt_j$ containing the shifted operation. $\eqt_j$ does not necessarily need to be an on-time or active equality tree when \textsc{shift}() finishes, but we will show that $\eqt_j$ will satisfy the definition of a semi-active equality tree. We can imagine that operations are connected by a rubber band to their optimum, and that time constraints are mechanical locks that will push away connected operations. The \textsc{shift}() procedure works as if we were trying to move the given operation - we call it \emph{pivot} - with a finger and we slowly shift the operation to a new position. On the way, the shifted tree $\eqt_{pivot}$ can bump into other trees due to the locks and shift them together, and some parts of the tree can fall off due to the rubber bands. We will now describe, exactly how the \textsc{shift}() procedure works. The \emph{difference} in the distance between the current and desired position of operation $j$ is determined on line \ref{alg:shift:difference}. It is negative in the case of a backward shift and positive in case of forward shift. The \emph{direction} of shift remains unchanged during the whole shift --- $\eqt_j$ is shifted until the \emph{difference} is zero (line \ref{alg:shift:nodifference}) -- at this moment, desired position is reached and the procedure exits. During the shift, some parts of the tree $\eqt_j$ can "fall off" (i.e. a split event) or the tree can "bump" into another tree (i.e. a merge event). The upcoming event is determined on line \ref{alg:shift:getnearestevent}. The event is a tuple consisting of the temporal constraint causing the event, time (i.e. start of the tree where the event occurs) and type of event (\emph{split} or \emph{merge}). A shift of the tree is performed as a sequence of such events until the desired position is reached (it is verified whether the desired position or the next event position is nearer on line \ref{alg:shift:nearer}). 

A split event can occur when a temporal constraint $(k,l)$ in tree $\eqt_j$ becomes inactive. At this moment $\eqt_j$ is split into $\eqtback{(k,l)}$ and $\eqtforw{(k,l)}$ (line \ref{alg:shift:split}) and only the part containing operation $j$ is shifted further. 

A merge event occurs whenever a temporal constraint $(k,l)$ would become violated if $\eqt_j$ was shifted further. At this moment trees $\eqt_k$ and $\eqt_l$ are merged, and from this moment on they will be shifted together (line \ref{alg:shift:merge}). Thus, a further shift of $\eqt_j$ no longer violates the temporal constraint $(k,l)$. The existence of a feasible solution is checked by the detection of a negative cycle\footnote{An STN is consistent if the distance graph does not contain a negative cycle (see \citet{dechtermeiripearl:ai:1991})} on line \ref{alg:shift:solustionexistencycheck}.

\begin{algorithm}
\caption{Shifting of activity $i$ to a postition satisfying the given criteria}\label{alg:shift}
\begin{algorithmic}[1]
\Procedure{shift}{$j$, $\mathit{criteria}$, $(i,j)$}\Comment $j$ is the pivot
	\State difference $\gets$ distance necessary for $j$ to satisfy criteria\label{alg:shift:difference}
	\If {$\mathit{difference}<0$} 
		\State $\mathit{direction} \gets$ backwards
	\Else 
		\State $\mathit{direction} \gets$ forwards
	\EndIf	
	\While{$\mathit{difference} <> 0$}\label{alg:shift:nodifference}
		\State $\mathit{event} \gets$ \textsc{getNearestEvent}($j$, $\mathit{direction}$)\label{alg:shift:getnearestevent}
		\If{event exists}
			\State $\mathit{eventDifference} \gets \mathit{time(event)} -\eqt_j$
			\If{$abs(\mathit{eventDifference}) < abs(\mathit{difference})$} \label{alg:shift:nearer}
				\State $\sigma(\eqt_j) \gets \sigma(\eqt_j)+\mathit{eventDifference}$
				\Switch{type(event)}
					\Case{split}
						\State \textsc{split}($\mathit{temporalconstraint(event)}$)\label{alg:shift:split}
					\EndCase				
					\Case{merge}
						\State \textsc{merge}($\mathit{temporalconstraint(event)}$)\label{alg:shift:merge}
						\If{not $(i,j)$ is nothing}
							\If{$\eqt_i = \eqt_j$ \textbf{and} $(i,j)$ is violated \textbf{and} there exists a path from $j$ to $i$ in $\eqt_j$}\label{alg:shift:solustionexistencycheck}
								\State \textsc{makeTreeOnTime}($\eqt_j$) \Comment{rollback changes}
								\State throw error 'Solution doesn't exist'
							\EndIf
						\EndIf
					\EndCase
				\EndSwitch
			\Else
				\State $\sigma(\eqt_j) \gets \sigma(\eqt_j)+\mathit{difference}$
			\EndIf			
		\Else
			\State $\sigma(\eqt_j) \gets \sigma(\eqt_j)+\mathit{difference}$
		\EndIf
		
		\State $\mathit{difference} \gets$ shift necessary for $j$ to satisfy criteria
	\EndWhile
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Splitting an equality tree at a given termporal constraint}\label{alg:split}
\begin{algorithmic}[1]
\Procedure{split}{$(i,j)$}
	\State $\f_{\s} \gets \f_{\s} - \eqt_{i}$ \Comment{we assume $\eqt_{i}=\eqt_{j}$}
	\State $\f_{\s} \gets \f_{\s} \cup \eqtback{(i,j)} \cup \eqtforw{(i,j)}$
\EndProcedure
\end{algorithmic}
\end{algorithm}	

\begin{algorithm}
\caption{Merging two equality trees at a given termporal constraint}\label{alg:merge}
\begin{algorithmic}[1]
\Procedure{merge}{$(i,j)$}
	\State $\f_{\s} \gets \f_{\s} - (\eqt_{i} \cup \eqt_{j})$ \Comment{remove trees containing $i$ and $j$ from $\f_{\s}$}
	\State $\f_{\s} \gets \f_{\s} \cup \{(\act_{\eqt_{i}} \cup \act_{\eqt_{j}}, A_{\eqt_{i}} \cup A_{\eqt_{j}} \cup \{(i,j)\})\}$ \Comment{add merged tree into $\f_{\s}$}
\EndProcedure
\end{algorithmic}
\end{algorithm}	

Procedure \textsc{getNearestEvent}() (see algorithm \ref{alg:getnearestevent}) consists of the calling of two procedures: \textsc{getNearestSplitEvent}() and \textsc{getNearestMergeEvent}(), and returns the event nearest to the start of $\eqt_i$. If no event is found, nothing is returned.

\begin{algorithm}
\caption{Finding the nearest event}\label{alg:getnearestevent}
\begin{algorithmic}[1]
\Procedure{getNearestEvent}{$i$, $\mathit{direction}$}
	\State $\mathit{splitEvent} \gets$ \textsc{getNearestSplitEvent}($i, \mathit{direction}$)
	\State $\mathit{mergeEvent} \gets$ \textsc{getNearestMergeEvent}($i, \mathit{direction}$)
	\State	
	\State\Return $\mathit{splitEvent}$ or $\mathit{mergeEvent}$ with $time(event)$ nearer to $\sigma(\eqt_i)$
\EndProcedure
\end{algorithmic}
\end{algorithm}	

Procedure \textsc{getNearestSplitEvent}() (see algorithm \ref{alg:getnearestsplitevent}) finds the split event nearest to the start of $\eqt_i$ in the given direction. Branches created by time constraints leading from/to the pivot task are searched by \textsc{findNearestSplitEvent}(). This procedure returns the cost function of the subtree defined by the given time constraint and the parameter $\mathit{opposite}$. The calculation is made recursively (see lines \ref{alg:findnearestsplitevent:costFn1}, \ref{alg:findnearestsplitevent:costFn2} and \ref{alg:findnearestsplitevent:costFn3}) and the nearest split event is remembered in the parameter $\mathit{event}$ (see line \ref{alg:findnearestsplitevent:nearest}). Let us note that as a side effect the outer-most temporal constraint with the same split-time found in the same branch is returned in $\mathit{temporalconstraint(event)}$. This ensures that the parts falling off the shifted tree are active quality trees and not just semi-active equality trees.

\begin{algorithm}
\caption{Finding the nearest split event}\label{alg:getnearestsplitevent}
\begin{algorithmic}[1]
\Procedure{getNearestSplitEvent}{$i$, $\mathit{direction}$}
	\State $\mathit{nearestSplitEvent}\gets nothing$\Comment $\mathit{nearestSplitEvent}$ is filled in by $\mathit{findNearestSplitEvent}()$
	\State
	\For{each $(i,j)\in O_{A_{\eqt_{i}}}$}
		\State $\mathit{findNearestSplitEvent}((i,j), \mathit{false}, \mathit{nearestSplitEvent},$ $\mathit{direction})$\label{alg:getnearestsplitevent:branches1}
	\EndFor
	\State
	\For{each $(k,i)\in O_{A_{\eqt_{i}}}$}
		\State $\mathit{findNearestSplitEvent}((k,i), \mathit{true}, \mathit{nearestSplitEvent},$ $\mathit{direction})$\label{alg:getnearestsplitevent:branches2}
	\EndFor
	\State
	\State\Return $\mathit{nearestSplitEvent}$;
\EndProcedure
\end{algorithmic}
\end{algorithm}	

\begin{algorithm}
\caption{Finding the nearest split event in a subtree}\label{alg:findnearestsplitevent}
\begin{algorithmic}[1]
\Procedure{findNearestSplitEvent}{$(i,j), \mathit{opposite}, \&\mathit{event}, \mathit{direction}$}
	\State\Comment parameter $\mathit{event}$ is passed "by reference" and it stores the nearest event found so far
	\State $costFn = 0$\Comment{Cost function of the subtree}
	\State
	\If{$\mathit{opposite}$}
		\State $task \gets i$
	\Else
		\State $task \gets j$
	\EndIf
	\State	
	\For{each $(task,k)\in O_{A_{\eqt_{task}}}$}
		\If{$(task,k)\neq (i,j)$}\Comment{We do not want to go back}
			\State $costFn = costFn +$\State\hspace{5pt}$+\mathit{findNearestSplitEvent}((task,k), \mathit{false}, \mathit{event}, \mathit{direction})$\label{alg:findnearestsplitevent:costFn1}
		\EndIf
	\EndFor
	\State
	\For{each $(k,task)\in O_{A_{\eqt_{task}}}$}
		\If{$(k,task)\neq (i,j)$}\Comment{We do not want to go back}
			\State $costFn = costFn +$\State\hspace{5pt}$+\mathit{findNearestSplitEvent}((k,task), \mathit{true}, \mathit{event}, \mathit{direction})$\label{alg:findnearestsplitevent:costFn2}
		\EndIf
	\EndFor
	\State	
	\State $\mathit{costFn} = \mathit{costFn} + c_{task}$\label{alg:findnearestsplitevent:costFn3}
	\State
	\If{$(\mathit{direction}=backwards$ \textbf{and not} $\mathit{opposite})$ \textbf{or}\\\hspace{24pt} $(\mathit{direction}=forwards$ \textbf{and} $\mathit{opposite})$}\Comment{Only this condition allows a split event}
		\State $\mathit{splitTime}=\argmin_{t}{\{\mathit{costFn(t)}\}}$
		\If{$\mathit{splitTime}$ is nearer than $\mathit{time}(\mathit{event})$}\label{alg:findnearestsplitevent:nearest}
			\State $\mathit{type}(\mathit{event}) \gets \mathit{split}$
			\State $\mathit{temporalconstraint}(\mathit{event}) \gets (i,j)$	
			\State $\mathit{time}(\mathit{event}) \gets \mathit{splitTime}$		
		\EndIf
	\EndIf
	\State
	\State\Return $\mathit{costFn}$
\EndProcedure
\end{algorithmic}
\end{algorithm}	


Procedure \textsc{getNearestMergeEvent}() returns the nearest event, in which $\eqt_i$ bumps into another tree. It goes through all edges leading from $\eqt_i$ into another tree in case of a forward shift (lines \ref{alg:getnearestmergeevent:foreachk} and \ref{alg:getnearestmergeevent:foreachkl}). Whenever $\eqt_i$ touches another tree (line \ref{alg:getnearestmergeevent:mergetime}), a precedence constraint would be violated if $\eqt_i$ was shifted further.

\begin{algorithm}
\caption{Finding the nearest merge event}\label{alg:getnearestmergeevent}
\begin{algorithmic}[1]
\Procedure{getNearestMergeEvent}{$i$, $\mathit{direction}$}
	\State $\mathit{nearestMergeEvent}\gets \mathit{nothing}$
	\State
	\Switch{$\mathit{direction}$}
		\Case{forwards}
			\State $\mathit{time} \gets \infty$
			\For{each $k$ in $\act_{\eqt_i}$} \label{alg:getnearestmergeevent:foreachk}
				\For{each $(k,l)\in A_{\s}$}\label{alg:getnearestmergeevent:foreachkl}
					\If{$\eqt_k \neq \eqt_l$}
						\State $\mathit{mergeTime} \gets \sigma(l)-p_{kl}-(\sigma(\eqt_k)-\sigma(k))$\label{alg:getnearestmergeevent:mergetime}
						\If{$\mathit{mergeTime} < \mathit{time}$}
							\State $\mathit{time} \gets \mathit{mergeTime}$
							\State $\mathit{type}(\mathit{nearestMergeEvent}) \gets \mathit{merge}$
							\State $\mathit{temporalconstraint}(\mathit{nearestMergeEvent}) \gets (k,l)$	
							\State $\mathit{time}(\mathit{nearestMergeEvent}) \gets \mathit{mergeTime}$
						\EndIf
					\EndIf
				\EndFor
			\EndFor
		\EndCase
		\Case{backwards}
			\State analogical to forward case...
		\EndCase
	\EndSwitch	
	\State
	\State\Return $\mathit{nearestMergeEvent}$;
\EndProcedure
\end{algorithmic}
\end{algorithm}	

A merge event causes the merging of trees connected by \textit{temporalconstraint}{(event)} in procedure \textsc{shift}() on line \ref{alg:shift:merge}. Let us note, that when, for example, the attached tree has a partially constant cost function, the merged tree does not need to be an active equality tree, because the connecting temporal constraint is not active. It is not hard to see that this tree is an on-time semi-active equality tree. Let us assume the forward shift of some $\eqt_j$. All other trees merged with $\eqt_j$ were on-time active equality trees before merging. Thus these trees (now parts of $\eqt_j$) could not become strictly early during the forward shift. At the same time, all parts of $\eqt_j$, which became on-time were split. Thus tree $\eqt_j$ is an also c-on-time semi-active equality tree. According to this fact, procedure \textsc{activate}() (see algorithm \ref{alg:activate}) splits $\eqt$ into more on-time active equality trees.

\begin{algorithm}
\caption{Splitting on-time weakly active equality tree into on-time active equality trees}\label{alg:activate}
\begin{algorithmic}[1]
\Procedure{activate}{$\eqt$}
	\State $\widetilde{A} \gets A_{\eqt}$
	\For{each $(i,j)\in \widetilde{A}$}
		\If{($\eqt_i$ is on-time) $and$ ($\eqt_j$ is on-time)}
			\State $\textsc{split}((i,j))$
		\EndIf
	\EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}	

Since procedures which remove operations and temporal constraints from $\s$ are not necessary for the purpose of this article, they are not described. Their implementation is analogical to procedures which inserts operations and temporal constraints, but in the inverse order of steps.

\subsection{Complexity and finiteness of the algorithm}
\subsubsection{Finiteness of the algorithm}
We will now show, that the presented algorithm is finite. This means that it ends after a finite number of steps. It is obvious that the only place where the algorithm could get stuck in an infinite loop is the function \textsc{shift}(). Let us analyze this function more deeply.

The tree is either shifted closer to the desired position or its position remains unchanged in each cycle of the while loop in the procedure \textsc{shift}() on line \ref{alg:shift:difference}. The loop can get stuck in a cycle only in cases when the difference remains unchanged and an infinite sequence of split and merge events occurs. Let us assume that the variable \emph{direction}=\emph{forwards}, and let us consider some $\eqtback{(k,l)}$ that has been split from $\eqt_j$. Either there exists a negative cycle in the problem instance and the procedure ends with an error on line \ref{alg:shift:solustionexistencycheck}, or no negative cycle is present and nothing forces $\eqtback{(k,l)}$, separated from $\eqt_j$, to be merged with $\eqt_j$ again while the variable \emph{difference} remains unchanged. Thus an infinite loop of merge and split events never occurs.

\subsubsection{Complexity of the algorithm}
The minimum of an arbitrary convex function could be found numerically (see \cite[pp. \,492--496]{Press:2007:NRE:1403886}). Even though it is an $O(1)$ operation, according to the size of the problem, it takes a lot of computational time in practice. If specific convex functions (i.e. partially linear functions or quadratic functions) are used, the minimum can be calculated practically much faster. The argument of the minimum of these functions could be in $\pm\infty$. In order to solve this problem, lower and upper bound was used for the time scale.

Let us denote $|\act|=n$ and $|A|=m$. At most $O(m)$ time constraints are checked in \textsc{getNearestSplitEvent}() (incl. \textsc{findNearestSplitEvent}()). Each calculation of \emph{costFn} in \textsc{findNearestSplitEvent}()) takes time $O(n)$ for general convex cost functions. Thus \textsc{getNearestSplitEvent}() takes time $O(mn)$.

\textsc{getNearestMergeEvent}() must check $O(m)$ time constraints. Thus \textsc{getNearestMergeEvent}() takes time $O(m)$.

It easily follows, that \textsc{getNearestEvent()} takes time $O(mn)$.

There are $m$ temporal constraints, thus there can be at most $m$ merge and $m$ split events (i.e. cycles of the loop) in the procedure \textsc{shift}(). \textsc{getNearestEvent}() is called in each cycle, thus procedure \textsc{shift}() takes time $O(m^2n)$.

The procedure \textsc{shift}() is called during the insertion of each temporal constraint. Thus \textsc{insertTemporalConstraint}() takes time $O(m^2n)$. The procedure \textsc{insertOperation}() uses also \textsc{shift}(), but the inserted operation is not connected by any temporal constraint. Thus the procedure \textsc{insertOperation}() takes time $O(1)$ (the tree is just shifted in its optimum). If follows that the whole algorithm has complexity $O(m^3n)$.

Whenever quadratic cost functions are used, \textsc{getNearestSplitEvent}() only takes time $O(m)$, because each calculation of \emph{costFn} consists of updating of quadratic coefficients, and thus it only takes $O(1)$ now. The whole algorithm then takes $O(m^2n)$.

\subsection{Source code}
An open source java library, implementing an above-described algorithm, can be found at \url{http://code.google.com/p/switco/.}

\section{Conclusions}
We introduced a condition guaranteeing the optimality of a schedule with time constraints and convex cost functions. Based on this condition, an algorithm was designed that builds an optimal schedule in polynomial time. This algorithm was also implemented as a Java library. Since the introduced problem doesn't concern resources, further work will concentrate on extending the algorithm to solve the problem with unary resources as well.

\appendix

\section{Appendix}\label{sec:appendix}
\subsection{Example of \textsc{insertTemporalConstraint}()}\label{sec:example}
An example of one call of the procedure \textsc{insertTemporalConstraint}() can be found in figure \ref{fig:example}. To make the example simpler, we abstract from exact cost functions and just imagine that each operation tends to reach some optimum - represented by star marks * on corresponding rows in the figure - as if these operations were on a rubber band connected with theirs optimum. For a better imagination, the procedure is shown in terms introduced in section \ref{sec:problemdefinition} instead of the terms of STNCONV.

Let us assume that we already have some schedule (see figure \ref{fig:example:first} step $0$) and are about to insert temporal constraint $(2,4)$ into this schedule. Dashed circles in figure \ref{fig:example} describe the trees in $\f_{\s}$. All temporal constraints $(i,j)$ except $(6,4)$ have $d_{ij}=\infty$ and only $d_{64}=1$. 

Since constraint $(2,4)$ would be violated, we must shift tree $\eqt_{4}$ forward (steps $1-4$ correspond with the calling of \textsc{shift}($4, \sigma(4)=6, (2,4)$) in the algorithm \textsc{insertTemporalConstraint}() on line \ref{alg:insertTemporalConstraint:shift}). Afterwards $\eqt_{4}$ is shifted into its optimum (steps $5-6$ correspond with the calling of \textsc{makeTreeOnTime}($\eqt_{4}$) in the algorithm  \textsc{insertTemporalConstraint}() on line \ref{alg:insertTemporalConstraint:makeontime}). Finally, tree $\eqt_{4}$ is split into two active equality trees in step $7$, which corresponds with the calling of the procedure \textsc{optimize}($\eqt_4$) in the algorithm  \textsc{insertTemporalConstraint}() on line \ref{alg:insertTemporalConstraint:activate}.

\noindent\textbf{Step 0}: We are in a starting position with the following trees in $\f=\{\{1,2\}$, $\{3,4\}$, $\{5\}$, $\{6\}$\}. Operation $4$ (thus the whole tree $\eqt_{4}=\{3,4\}$) must be shifted forward, otherwise temporal constraint $(2,4)$ would be violated. \\
\textbf{Step 1}: During the shift of tree $\eqt_{4}$, a merge event on temporal constraint $(6,4)$ occurs. Thus trees $\{3,4\}$ and $\{6\}$ are being merged. It now follows that $\eqt_{4}=\{3,4,6\}$.\\
\textbf{Step 2}: The next event during the shift of $\eqt_{4}$ is a split event. Since activity $3$ reaches its optimum, temporal constraint $(3,4)$ would no longer be active. Thus $\eqt_{4}=\{4,6\}$ now.\\
\textbf{Step 3}: Analogically to step 1: Trees $\{4,6\}$ and $\{5\}$ must be merged. Thus $\eqt_{4}=\{4,5,6\}$.\\
\textbf{Step 4}: Operation $4$ reaches the time point where temporal constraint $(2,4)$ is no longer violated and can be inserted into $A_{\s}$.\\
\textbf{Step 5}: Tree $\eqt_{4}$ is being shifted backwards in order to reach its optimum. A merge event on temporal constraint $(2,4)$ occurs, thus $\eqt_{4}=\{1,2,4,5,6\}$.\\
\textbf{Step 6}: Tree $\eqt_{4}$ reaches its optimum.\\
\textbf{Step 7}: The procedure \textsc{activate}($\eqt_{4}$) splits $\eqt_{4}$ into trees $\{1,2,4,6\}$ and $\{5\}$. All trees in $\f_{\s}$ are now on-time active equality trees, and no precedence is violated.

\begin{figure*}
	\figuretopcaptrue
	\caption{Example}\label{fig:example}
	\centering
		\subfigure[Step 0]{						
			\includegraphics[scale=0.5]{Fig5a}
			\label{fig:example:first}
		}
		\subfigure[Step 1]{
			\includegraphics[scale=0.5]{Fig5b}
			\label{fig:example:second}			
		}
		\subfigure[Step 2]{
			\includegraphics[scale=0.5]{Fig5c}
			\label{fig:example:third}			
		}			
		\subfigure[Step 3]{
			\label{fig:example:fourth}
			\includegraphics[scale=0.5]{Fig5d}
		}
		\subfigure[Step 4]{
			\label{fig:example:fifth}
			\includegraphics[scale=0.5]{Fig5e}
		}
		\subfigure[Step 5, 6 and 7]{
			\label{fig:example:sixth}
			\includegraphics[scale=0.5]{Fig5f}
		}					
\end{figure*}

\subsection{Counterexample of why a weakly active equality tree does not guarantee optimality}\label{sec:counterexample}
In \citet{Chretienne:2003:PSC:642013.642023}, only a weaker form of an active edge is used (in this article defined as \emph{weakly active edge} and \emph{weakly active equality tree}). Thus edge $(i,j)\in \aqg$ is also active if both $\eqtback{(i,j)}$ and $\eqtforw{(i,j)}$ are on-time. But it is easy to see that the schedule described in figure \ref{fig:aktivityVM} with cost functions\footnote{Cross in the figure \ref{fig:aktivityVM} represents the optimum for each operation.} shown in figure \ref{fig:costfunctionsVM} is not optimal, even though it satisfies the optimality condition defined in \citet{Chretienne:2003:PSC:642013.642023} - it is an on-time semi-active equality tree, because the edge between trees $\{i\}$ and $\{j,k\}$ is weakly active and both trees are on-time and the same holds for the edge between trees $\{j\}$ and $\{i,k\}$, but it does not satisfy the definition of c-on-time semi-active equality tree. 

\begin{figure}[h]
\caption{Problematic operations structure}\label{fig:aktivityVM}
\centering 
\includegraphics[scale=0.6]{Fig6}
\end{figure}
\begin{figure}[h]
\caption{Cost functions in problematic operations structure}\label{fig:costfunctionsVM}
\centering 
\includegraphics[scale=0.4]{Fig7}
\end{figure}

With the definition of active edge introduced in this paper, it is possible to cover this graph with only three disjoint active equality trees (each tree consists of one operation), where the tree containing operation $k$ is not on-time and thus the schedule is not recognized as optimal.

\section*{Acknowledgements}
Research is supported by the Czech Science Foundation under the project P202-10-1188

\bibliographystyle{abbrvnat}
\bibliography{bibliography}{}


\end{document}